package leetcode.Hot100;

import java.util.Objects;
import java.util.Stack;

/**
 * @author Cheng Jun
 * Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']'  的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * <p>
 * 来源：力扣（LeetCode）20. 有效的括号
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * @version 1.0
 * @date 2021/11/23 21:36
 * bilibili 的笔试题
 */
public class isValid {

    public static void main(String[] args) {
        System.out.println(isValid("()"));
        System.out.println(isValid1("()"));
    }

    public static boolean isValid(String s) {
        Stack<String> brackets = new Stack<>();
        for (String bracket : s.split("")) {
            if (brackets.isEmpty()) {
                brackets.add(bracket);
            } else {
                if (Objects.equals(bracket, "(") || Objects.equals(bracket, "[") || Objects.equals(bracket, "{")) {
                    brackets.add(bracket);
                } else {
                    switch (bracket) {
                        case ")":
                            if (Objects.equals(brackets.peek(), "(")) {
                                brackets.pop();
                            } else {
                                brackets.add(bracket);
                            }
                            break;
                        case "]":
                            if (Objects.equals(brackets.peek(), "[")) {
                                brackets.pop();
                            } else {
                                brackets.add(bracket);
                            }
                            break;
                        case "}":
                            if (Objects.equals(brackets.peek(), "{")) {
                                brackets.pop();
                            } else {
                                brackets.add(bracket);
                            }
                            break;
                    }
                }
            }
        }
        return brackets.isEmpty();
    }

    static boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
